6.8 KB · ⇊ 4 parts · ⤓ Micron 6.8 KB · ⤓ HTML 25.1 KB

top

In computational mathematics, a matrix-free method is an algorithm for solving a linear system of equations or an eigenvalue problem that does not store the coefficient matrix explicitly, but accesses the matrix by evaluating matrix-vector products.cite-ref-1[1] Such methods can be preferable when the matrix is so big that storing and manipulating it would cost a lot of memory and computing time, even with the use of methods for sparse matrices. Many iterative methods allow for a matrix-free implementation, including:

• the power method,

• the Lanczos algorithm,cite-ref-2[2]

• Locally Optimal Block Preconditioned Conjugate Gradient Method (LOBPCG),cite-ref-3[3]

• Wiedemann's coordinate recurrence algorithm,cite-ref-4[4]

• the conjugate gradient method,cite-ref-5[5]

• Krylov subspace methods.

Distributed solutions have also been explored using coarse-grain parallel software systems to achieve homogeneous solutions of linear systems.cite-ref-6[6]

It is generally used in solving non-linear equations like Euler's equations in computational fluid dynamics. Matrix-free conjugate gradient method has been applied in the non-linear elasto-plastic finite element solver.cite-ref-7[7] Solving these equations requires the calculation of the Jacobian which is costly in terms of CPU time and storage. To avoid this expense, matrix-free methods are employed. In order to remove the need to calculate the Jacobian, the Jacobian vector product is formed instead, which is in fact a vector itself. Manipulating and calculating this vector is easier than working with a large matrix or linear system.

cite-note-11. ↑ citereflangvillemeyer2006Langville, Amy N.; Meyer, Carl D. (2006), Google's PageRank and beyond: the science of search engine rankings, Princeton University Press, p. 40, ISBN 978-0-691-12202-1

cite-note-22. ↑ citerefcoppersmith1993Coppersmith, Don (1993), "Solving linear equations over GF(2): Block Lanczos algorithm", Linear Algebra and Its Applications, 192: 33–60, doi:10.1016/0024-3795(93)90235-G

cite-note-33. ↑ citerefknyazev2001Knyazev, Andrew V. (2001). "Toward the Optimal Preconditioned Eigensolver: Locally Optimal Block Preconditioned Conjugate Gradient Method". SIAM Journal on Scientific Computing. 23 (2): 517–541. Bibcode:2001SJSC...23..517K. CiteSeerX 10.1.1.34.2862. doi:10.1137/S1064827500366124.

cite-note-44. ↑ citerefwiedemann1986Wiedemann, D. (1986), "Solving sparse linear equations over finite fields" (PDF), IEEE Transactions on Information Theory, 32: 54–62, doi:10.1109/TIT.1986.1057137

cite-note-55. ↑ citereflamacchiaodlyzko1991Lamacchia, B. A.; Odlyzko, A. M. (1991), "Solving Large Sparse Linear Systems Over Finite Fields", Advances in Cryptology – CRYPT0' 90, Lecture Notes in Computer Science, vol. 537, p. 109, doi:10.1007/3-540-38424-3_8, ISBN 978-3-540-54508-8

cite-note-66. ↑ citerefkaltofenlobo1996Kaltofen, E.; Lobo, A. (1996), "Distributed Matrix-Free Solution of Large Sparse Linear Systems over Finite Fields", Algorithmica, vol. 24, no. 3–4, pp. 311–348, CiteSeerX 10.1.1.17.7470, doi:10.1007/PL00008266, S2CID 13305650

cite-note-77. ↑ citerefprabhunekrishnan2020Prabhune, Bhagyashree C.; Krishnan, Suresh (4 March 2020). "A fast matrix-free elasto-plastic solver for predicting residual stresses in additive manufacturing". Computer Aided Design. 123: 102829. doi:10.1016/j.cad.2020.102829.